\section{Introducción teórica}

A modo de introducción del presente trabajo, procederemos a describir en forma breve y concisa la teoría que sustenta la implementación de \emph{Autocaras}. Por un lado, hablaremos del \emph{análisis de componentes principales} que nos permitirá obtener una relación fiel entre las variables involucradas (en nuestro caso, la dimensión de la imagen en cuestión). Mencionaremos también la importancia del problema de los autovalores y como los obtuvimos mediante métodos iterativos.

\subsection{Autovalores y autovectores}

Recordemos que sea $A$ una \emph{transformación lineal} y $x$ un vector \/ $x \neq 0$, se dice que $x$ es un \emph{autovector} de $A$ si se cumple:
$$ A x = \lambda x$$ \\ 
(para cierto $\lambda \in \mathbb{R} $ que se lo llama \emph{autovalor} del correspondiente \emph{autovector} $x$)

Autovectores y autovalores son conceptos fundamentales del álgebra lineal y que tienen diversas aplicaciones en distintos campos de la ciencia; ya sea desde análisis de datos (entre ellos, el análisis de componentes que describiremos más adelante), hasta ser pilares de la mecánica cuántica (por ej., en la \emph{ecuación de Schrödinger}), pasando por su rol en el diseño de estructuras en el que son utilizados para modelar las frecuencias de vibración de las mismas. 

\subsection{El método QR}

El algoritmo ``QR'' es un método iterativo desarrollado por John G. F. Francis y Vera Kublanovskaya, que consiste en aplicar de manera conveniente la factorización QR de una matriz A de tal manera de calcular los autovalores y autovectores de la misma sin pasar por otros métodos computacionalmente más costosos y/o numéricamente inestables. 

El algoritmo se describe a continuación como:
$$ A = Q_1 R_1 = A_1 $$ 
$$ A_2 = R_1 Q_1 $$  (multiplicamos en orden inverso)  
$$ A_2 = Q_2 R_2 $$  (factorizamos nuevamente)  
$$ A_3 = R_2 Q_2 $$  (hallamos $A_3$ de la misma manera que lo hicimos con $A_2$ ) 

\medskip
\pagebreak
En general para la \emph{k+1-ésima} iteración,
$$A_{k+1} = R_k Q_k $$\; \; \; \; \; \; \; \;  \hfill ($k = 1,2,3, ... $) 

La particularidad de este método es que para un número importante de matrices converge, es decir: 
$$ \lim_{k \rightarrow \infty} \: A_k = Q \varLambda $$
donde $\varLambda$ es una matriz diagonal con los autovalores de la matriz $A$ (simétrica) y donde las columnas de $Q$ son los autovectores de $A$. En nuestro trabajo, trabajamos con $A$ matriz simétrica, por ende vale esa descomposición particular. De todas maneras, dicho método vale para matrices no simétricas, solo que en principio, se puede asegurar que si convergen lo hacen a una matriz triangular superior $V$ que en su diagonal tiene los autovalores de $A$ que luego se usarán para hallar los autovectores de la misma. 

El coste computacional de este método es de $\approx O(n^3)$ por iteración.

Un detalle no menos importante de este método, es que al ser iterativo es necesario elegir un buen criterio de parada para el algoritmo. Ejemplos de estos criterios podrían ser el de parar luego de $m$ iteraciones o bien, el usado en esta oportunidad, que usa fuertemente la convergencia del método a una matriz triangular superior. Entonces se elige un $\delta$ de manera tal que el método termine una vez que la suma de los elementos que están por debajo de la diagonal sea menor que el parámetro elegido, matemáticamente sería pedir que:
%$$ \sum a_{i,j} \: \leq \: \delta \;\;\; \forall \;\; 1 \leq i < j \leq n $$
$$ \sum^n_{i = 2} {\sum^{i-1}_{j=1} {|a_{ij}|}} < \delta $$


\subsection{Análisis de componentes principales}

El \emph{análisis de componentes principales} es un procedimiento estadístico que permite dado un conjunto de datos multivariado, que puede ser en principio muy grande, conocer la relación entre los distintos ejemplares de la población a ser estudiada. Esta técnica reduce la dimensionalidad de las muestras y prioriza la existencia de aquellas variables que, de alguna manera, aportan más información. Esto facilita el análisis de la variabilidad de los datos y resalta las características más importantes de éstos. 

Para poder realizar esta técnica de análisis es necesario obtener los autovectores de la \emph{matriz de covarianza} de los datos. La matriz de covarianza se define como:
$$ M = \frac{1}{n-1} \: \sum^n_{i=1} (x_i-\mu)(x_i-\mu)^T $$ 
donde $\mu = \frac{1}{n} \: \sum^n_{i=1} x_i $, (promedio de las imágenes).

Luego de obtener la matriz $M$, se procede a calcular los autovectores de la misma. Sean estos autovectores: $v_1, v_2, ... , v_n $ (ordenados de mayor a menor según el valor en módulo de sus respectivos autovalores, se define entonces la $tc(x)$, transformación característica como:
$$ tc(x_i) = ( v^T_1 x_i, v^T_1 x_2, ... , v^T_k x_i) \in \mathbb{R}^k \: \text{ \emph{donde se cumple que:} } k \leq n $$
y donde $k$ representa la cantidad de componentes sobre las cuales se proyectan los datos originales.

En resumen, lo que nos permite la $tc(x)$ es proyectar las imágenes en otro espacio de coordenadas. La transformación nos servirá para aplicarla luego a una imagen nueva y de esta manera determinar que tan cerca o lejos está del conjunto de datos conocidos. Para ello introduciremos el siguiente concepto denominado \emph{distancia de Mahalanobis}. 

\pagebreak
\subsection{Distancia de Mahalanobis}

La distancia de Mahalanobis es una medida estadística de distancia introducida en 1936 por Prasanta Chandra Mahalanobis y se basa fuertemente en las correlaciones entre las variables involucradas. Esto es fuertemente usado en nuestra aplicación ya que nos permite con un grado de certeza alto conocer la relación entre la variable que queremos testear contra el grupo de datos conocidos.

Entonces se define a la distancia de mahalanobis entre un vector $x = (x_1, x_2, ... x_n)^T$ y un grupo de valores con media muestral $\mu = (\mu_1, \mu_2, ... , \mu_n)^T $ como:
$$ D_M(x) = \sqrt{ (x-\mu)^T S^{-1} (x-\mu) }  $$
(con $S^{-1}$ como la inversa de la matriz de covarianza).




